What are oversampling and rescoring in the context of binary quantization, and why are they necessary?

Oversampling and rescoring are the two techniques that make binary quantization usable. Binary quantization reduces each dimension to a single bit, so the quantized distance between two vectors is a very coarse approximation of the true distance. If you use it directly to rank a candidate set and take the top-k, you will get a ranking that is noisy near the decision boundary, and the true nearest neighbors will often be pushed out of the top-k by near-duplicates that happened to quantize favorably. Oversampling means retrieving more candidates than you actually need - say 3x or 5x the limit - using the fast quantized distance. Rescoring means taking that larger candidate set and re-ranking it using the full-precision vectors, which are still stored in the collection, to recover the accurate ordering. The combination is what gives BQ its characteristic profile: nearly the memory of binary, with recall close to full precision.

The mechanism is a classic retrieve-then-rerank pattern applied at the quantization layer. The quantized distance is good enough to separate the candidate set into approximately the right region of the space - it has high recall at the coarse level - but not good enough to order vectors that are close together. So you use it to cast a wide net, then you pay the cost of full-precision distance computation on a small number of candidates to get the final ordering. The oversampling factor is the key parameter: too low and the true nearest neighbors are not in the candidate set, so rescoring cannot recover them; too high and you pay for full-precision distance computations on candidates that had no chance. The right factor depends on the intrinsic dimensionality of the data and on how aggressive the quantization is. For binary quantization on 1024-dim normalized embeddings, an oversampling factor of 2-4 is typical. For lower-dimensional data or for higher compression schemes (sub-byte), you may need more.

The trade-off is recall against latency. Oversampling multiplies the candidate set size, which increases the cost of the rescoring step linearly. Rescoring adds a full-precision distance computation per candidate, which is 4x to 32x more expensive per comparison than the quantized distance, depending on the scheme. So the combination can be several times slower than a pure quantized search, but still much faster than full-precision HNSW over the whole collection - the point is that you are only rescoring a small candidate set, not the whole collection. The common mistake is enabling binary quantization without rescoring and concluding that BQ is unusable. BQ without rescoring is not a fair test; the whole design assumes rescoring is on. The second common mistake is setting the oversampling factor too high by default. Oversampling is cheap in memory but not in CPU, and on a high-QPS endpoint a factor of 10 can dominate the latency budget. Start at 2-3 and measure. The third mistake is forgetting that rescoring depends on full-precision vectors being stored. If your collection is configured to store only quantized vectors (e.g. to save disk), rescoring will silently fall back or fail depending on the version. Version note: the default oversampling factor and the exact semantics of QuantizationSearchParams have changed across Qdrant releases, so set them explicitly rather than relying on defaults.

Version-dependent: binary quantization, QuantizationSearchParams, and the oversampling field are all relatively recent additions to Qdrant and have continued to evolve. The exact default oversampling factor and whether rescoring is on by default differ by version. Always set both explicitly in performance-critical code, and re-benchmark after upgrading the server or the client.